0
Add your answer:
Earn +20 pts
How do you implement a deque using an array in c language?
A deque (pronounced deck) is a double-ended queue where objects can be efficiently pushed to and popped from either end of the queue.Arrays are not ideally suited to this task because arrays operate more efficiently when used like a stack, pushing and popping elements at the end of the array where the unused elements are. When we run out of unused elements we can reallocate the array creating more space at the end as required (typically doubling the allocation with each reallocation). For this we need to keep track of three pieces of information:The start address of the array.The overall length of the array in elements (size).The number of unused elements at the end of the array (space).A queue differs from a stack in that all insertions occur at the first unused element, while extractions occur at the first used element, which is initially at the start of the array. After an extraction we end up with an unused element at the start of the array. Although we could shunt all used elements by one element to eliminate the gap, it is more efficient to just keep track of the front of the queue. Thus we need 4 pieces of information:The start address of the array.The overall length of the array in elements (size).The total number of unused elements in the array (space).The index of the first element in the queue (start).From this information it is trivial to calculate the length of the queue (size-space) and thus determine where the first unused element is using modulo arithmetic: ((start+(size-space))%size).When we run out of space at the end of the array for an insertion, we simply use the unused elements at the beginning of the array. When we run out of space completely, we normalise the array so that the start of the queue is back at the beginning of the array before reallocating the array, thus placing all the new unused elements at the end of the array (after the last element in the queue). If we don't normalise the array, we will most likely end up with unused elements in the middle of the queue due to the circular nature of the array.To implement a deque we use a similar technique except we can insert and extract from either end of the queue. The following program demonstrates how the major deque operations can be implemented upon an array of unsigned integers.#include#include#include#include// a deque of unsigned integerstypedef struct arraydeque_t {unsigned* arr; // pointer to a variable length array of type unsignedunsigned sz; // overall length of array (in elements)unsigned space; // unused elementsunsigned start; // index of the start of the queue} arraydeque;bool is_empty (arraydeque*);unsigned size (arraydeque*);unsigned back (arraydeque*);unsigned front (arraydeque*);int initialise (arraydeque*);int push_back (arraydeque*, unsigned);int push_front (arraydeque*, unsigned);int expand (arraydeque*);void pop_back (arraydeque*);void pop_front (arraydeque*);void clear (arraydeque*);// calculates and returns the length of the queueunsigned size (arraydeque* deq) {return deq->sz-deq->space;}// returns true if the queue is emptybool is_empty (arraydeque* deq) {return deq->space==deq->sz;}// clear the dequevoid clear (arraydeque* deq) {if (deq->arr) free (deq->arr);memset (deq, 0, sizeof (arraydeque));}// initialise the dequeint initialise (arraydeque* deq) {const unsigned sz = 1; // start with 2 unused elementsmemset (deq, 0, sizeof (arraydeque));deq->arr = (unsigned*) malloc (sz * sizeof (unsigned));if (!deq->arr) return -1; // out of memorydeq->sz = sz;deq->space = sz;return 0;}// increase the size of the deque (create space)int expand (arraydeque* deq) {unsigned space, t, i, *p;if (deq->space) return 0; // no need to expand when we have space// normalise the array (realign the start of the queue with the start of the arraywhile (deq->start) {t = deq->arr[0]; // temporarily store first element valuefor (i=1; isz; ++i) // shunt all other elements forwarddeq->arr[i-1] = deq->arr[i];deq->arr[deq->sz-1] = t; // put temporary value at end of array--deq->start;}// reallocate the array to create space after the queuespace = (unsigned) (0.6 * deq->sz + 1); // optimum growth: 160%p = (unsigned*) realloc (deq->arr, (deq->sz + space) * sizeof(unsigned));if (!p) return -1; // out of memorydeq->arr = p;deq->sz += space;deq->space = space;return 0;}// insert value at the back of the queueint push_back (arraydeque* deq, unsigned val) {if (expand (deq))return -1; // out of memorydeq->arr[(deq->start+size (deq))%deq->sz] = val;--deq->space;return 0;}// insert value at the front of the queueint push_front (arraydeque* deq, unsigned val) {if (expand (deq))return -1; // out of memoryif (!deq->start)deq->start=deq->sz;--deq->start;deq->arr[deq->start] = val;--deq->space;return 0;}// extract the back valuevoid pop_back (arraydeque* deq) {++deq->space;}// extract the front valuevoid pop_front (arraydeque* deq) {++deq->start;deq->start%=deq->sz;++deq->space;}// return the back valueunsigned back (arraydeque* deq) {return deq->arr[((deq->start + size(deq)-1)%deq->sz)];}// return the front valueunsigned front (arraydeque* deq) {return deq->arr[deq->start];}// returns true or false at random (used by test program)bool is_true (void) {return rand() & 0x1;}// prints the content of the deque (used by test program)void print_queue (arraydeque* deq) {unsigned i, sz;printf ("{");sz = size (deq);i = deq->start;while (sz--) {printf ("%u%s", deq->arr[i++], sz?", ":"");if (i==deq->sz) i=0;}printf ("}\n");}// test programint main (void) {unsigned i, loop;srand((unsigned) time(0)); // seed random generatorarraydeque deq;initialise (&deq); // initialise the dequefor (loop=0; loop
What does DEQ stand for?
Department of Environmental Quality
You have misfiring on your integra what you need to do pass the deq?
the answers
How do you write a program to delete elements at both ends of a deque using C plus plus?
The C++ STL (Standard Template Library) provides a std::deque template specifically for this purpose: std::deque<int> deq {}; // default construct an empty deque of type int deq.push_back (42); // deq = {42} deq.push_front (0); // deq = {0, 42} deq.push_back (100); // deq = {0, 42, 100} deq.pop_front (); // deq = {42, 100} deq.pop_back (); // deq = {42} As with all other STL containers, any type or class that can be copy or move constructed can be placed in a std::deque, including other STL containers (even std::deque itself).
What if the catalytic coverter is not working?
you will get the check engine light on and not pass the dEQ
Which car equalizer has digital features?
The Pioneer DEQ-7600 is a Digital signal processor with EQ and spectrum analyzer
What is Michigan state gem?
Chlorastrolite http://www.michigan.gov/deq/0,1607,7-135-3311_4112_32722-112290--,00.html
How much does it cost to register car?
I just did it for $193 plus $21 for DEQ inspection on a '92 Ford Escort in the state of Oregon.
Where do you get a vehicle inspection?
If its for emissions testing, in Oregon you go to the DEQ, if you want your car inspected for general maintenance and repairs, take it to your mechanic.
Where can you dispose of trash in st tammany parish?
GREAT QUESTION! Looks like its in Slidell, and they have been trying to get the DEQ to close it for years. I cannot find another landfill in St Tammany Parish.
Program to delete elements at both ends in a dequeue using c plus plus?
#include<deque> std::deque<int> deq; deq.push_back (42); deq.pop_back (); deq.push_front (0); deq.pop_front ();
IPurchased car from private owner and put will pas deq on bill of sale and car wont pass deq found out within 2hrs and the owner wont give money back in Oregon do you have the right to your money back?
I don't know what the correct answer it, but I live in Oregon and know that the Attorney General consumer hotline may be able to answer it for you. The number is (1-877) 877-9392 or check out http://www.doj.state.or.us/finfraud/ to get answers. I am going through a similar situation with a used car I bought from Gresham Toyota. It wouldn't pass DEQ and the Ron Tonkin Nissan shop said the catalytic converter needed to be replaced but it was driveable. I can't seem to get any sympathy or help from Gresham Toyota, but I believe that cars cannot be sold unless they can pass DEQ, or there is some "as-is" agreement in the contract. Sounds like you covered yourself there, but it didn't work. Anyway, by the very next day, my car was ten times worse so we took it to another shop who verified that it needs an ENTIRE NEW ENGINE!!! I will be calling that attorney general number on my lunch break today. Good luck!
