/ * ================================================================================================================================================================ ===================== author: rerli time: 2004-02-11 purpose: learning queue =============== ============================================================================================================================================================================================================= ==== * // * Queue is a mathematical model from the abstract from the daily queue. Of course, the queue in the data structure is far without the flexibility in life. Queue regulations in the data structure: Data can only come from the tail, from the team. The data order that has entered the queue can no longer change. This is called "advanced first out" (FIFO) or "afterward" (LILO). One end that allows the insertion is called a queue, usually by a pointer called the tail pointer (REAR) to the tail element, that is, the tail pointer always points to the finally inserted element; one end of the allowable deletion is called a team, usually also used A team header (Front) pointing to the first position of the first element (of course, directly pointing to the first element, just in many data structures).
Similar to the queue, we can use a one-dimensional array to simulate the data structure of the queue, or you can simulate using the chain list.
According to the above description, the queue can sort out the following basic operations: 1. Creating an initialization: Pressing the fixed queue as an empty state. 2, into the queue: Add a new data item at the tail. 3, out of the queue: A data item is taken from the team and move the remaining items to the team. 4, queue empty: Judging whether the queue is empty. 5, queue full: Judging whether the queue is full. Conceptually, the queue does not exist in a "full" state, and its length can be arbitrarily increased, but there is always space limit in achieving (regardless of static or dynamic).
Let me discuss the queue structure with an array.
Assume that the type of element in the queue is T. The maximum length of the queue is queue_size. At any of the moment, the tail position is used with the subscript head, TAIL points.
The queue initial state should be: head = 0, TAIL = -1. Depending on the queue definition, the head value should be generated to 0, and each time the team is a data item, multiple movements must be performed (the remaining items move to the team). It is obvious that this structure cannot be used directly. To solve this problem, you can think of a solution from mathematics. For example, X = (x 1) MOD 100, the change ranges between [0,99], and more than 100 starts from 0, 1. This is not what we need! Many books are called "loop array" technology in many books. That is, when you enter the queue, move Tail first (ie, tail = (tail 1) mod que_size), move the head when you go out, first move the head (ie, head = (即 1) mod queue_size). In the movement, if the head (or tail) value is queue_size-1, the value of HEAD (or tail) is turned 0 after the movement, and this feature is a ring, as long as the array has space, you can enter the queue.
Using the "Cycling Array" to implement queues, you must pay attention to how to determine the empty and full state of the queue. In addition to the start state. Any time tail refers to an element that enters the queue, and Head refers to the position that the element just out of the queue is originally occupied. So (HEAD 1) MOD Queue_Size is the first element position in the current queue.
Conditions: (Tail 1) MOD Queue_Size == HEAD as the judgment condition for "queue full". In fact, there is an empty position in the queue, so that the queue uses space than the maximum space defined by one unit. If you use this unit, it is not good to determine "full" or "empty" (when head == tail), must catch up with TAIL, or HEAD catching TAIL to distinguish, so give processing Brought inconvenience.
* / # include
Typedef struct node {int data;} node;
#define len sizeof (node)
/ * Queue needs Variables * / type} BOOL; / * Define Bool Type * / unsigned int head; / * Definition team first standard Volume * / unsigned int tail; / * Define team tail * / static node * queue = null; / * Define a queue * / static unsigned int queue_size = 0; / * Queue size * /
/ * ======================== function: the size of the initialization queue returns: true or false ============= =========== * / bool initqueue (unsigned int size) {que = (node *) malloc (size * len); / * open space * / if (queue == null) / * open If the space fails, return false * / {return false;} queue_size = size; / * Save queue space size * / head = queue_size-1; / * team first standard value * / tail = queue_size-1; / * The tails are standard in the final value * / return true; / * Initialization success, return true * /} / * ====================== function: release The memory of the queue returns: void ================================ * / void FreeQueue () {free (queue); / * Note: This is important. Free () does not set Queue as NULL, so we must do it yourself. This prevents the "wild pointer", ie, an address uncertain pointer. * / Queue = null;}
/ * ========================== function: Determine if the queue is full: true or false ========== ================= * / bool full () {return ((tail 1)% queue_size == head);}
/ * =========================== function: Judgment the queue is empty back: true or false ========= =================== * / bool empty () {return (head == tail);
/ * ======================== function: into the queue return: True or false =============== ========= * / Bool Push (Node P) {if (! full ()) / * Queue is dissatisfied, then enter the queue; the tail is subsidized to add 1 * / {tail = (tail 1 )% queue_size; queue [tail] = p; return true;} else {printf ("Queue is overflow! / n"); return false;}} / * ============== ===== Function: Export queue returns: out of the queue element pointer ====================================================================================== * The queue is not available, then the queue; the team first standard should add 1 * / {head = (Head 1)% queue_size; Return (& queueue [head]);} else {printf ("Queue Is Empty! / N" Return null;}}}
Void main (void) {node node1 = {3}; node * p;
If (! initQueue (3)) / * Initialization is unsuccessful, exit * / {exit (0);} Push (Node1); / * Remove the following note, you can verify the interval of space use * / / * push (node1); push (node1); push (node1); * / p = POP (); Printf ("% d", p-> data);
Freequeue (); / * Note Pruning memory when procedure exits * /
Printf ("/ n"); system ("pause");}
