C language table stack and queue details and example code

C language table, stack, and queue details

Table ADT

Like A1 A2, A3... An table, the size of the table is n, and the size of the table is 0 is called empty table, non-empty table, Ai+1 successor Ai, Ai-1 precursor Ai, ADT related operation PrintList printing table elements; CreateEmpty creates an empty table; Find returns the location where the keyword first appeared; Insert and Delete insert and delete a keyword from a location in the table.

All operations on a table can be done using an array, but in this case using a linked list. A linked list (linked list) consists of a series of 1 structures that do not have to be connected in memory, each of which contains an element and a pointer to the structure that contains the element's successor. There are many kinds of linked list structure, one-way linked list, two-way linked list, circular linked list, list without table head, here to have table head node one-way linked list as an example, the other several implementation ideas are the same.

First, define the structure of the linked list:

struct Node 
{ 
 ElementType Element; 
 Node *Next; 
}; 

Table ADT main operations:

Node *CreateEmpty() 
{ 
 Node *header = new Node; 
 Header->Element = 0; 
 Header->Next = NULL; 
 return header; 
} 
void PrintList(Node *List) 
{ 
 Node *p = List->Next; 
 While (p) 
 { 
  std::cout << p->Element <<  "   " ; 
 } 
} 
Node *Find(Node *List, ElementType X) 
{ 
 Node *p = List->Next; 
 while(p && p->Element != X) 
 { 
  p = p->Next; 
 } 
 return p; 
} 
void Insert(Node *List, ElementType X) 
{ 
 Node *p = List; 
 while(p->Next) 
 { 
  p = p->Next; 
 } 
 p->Next = new Node; 
 p = p->Next; 
 p->Next = NULL; 
 p->Element = X; 
} 
void Delete(Node *List, ElementType X) 
{ 
 Node *p = List->Next; 
 Node *d = p->Next; 
 while(d->Element != X) 
 { 
p = p->Next; 
d = p->Next; 
 } 
 p->Next = d->Next; 
 delete d; 
} 

The above are the basic operations, you can see that the operation did not check whether the linked list is empty, there are hidden dangers in the delete operation.

Stack ADT

A stack (stack) is a table that restricts insertion and deletion to one location at the end of the table, called the top of the stack (top). The basic operations on the stack are Push (push on the stack) and Pop (push off the stack), the former being equivalent to insert and the latter to delete the last element inserted.

The implementation of the stack can be a pointer, or the use of an array, the implementation of the array has been described in the author's previous, this time using a single linked list.

First, the structure definition of the stack:

struct Stack 
{ 
 ElementType Element; 
 Stack *Next; 
}; 

Main operations of stack ADT:

Stack *CreateStack() 
{ 
 Stack *S = new Stack; 
 S->Next = NULL; 
 return S; 
} 
void Push(Stack *S, ElementType X) 
{ 
 Stack *p = new Stack; 
 p->Next = S; 
 S->Element = X; 
 S = p; 
} 
ElementType Pop(Stack *S) 
{ 
 Stack *p = S; 
 if(S->Next) 
 { 
S = S->Next; 
delete p; 
 } 
 return S->Element; 
} 

Queue ADT

Like stack 1, a queue is a table; however, when using a queue, insertion takes place at one end and deletion at the other. The basic operation of the queue is Enqueue (to join) and Dequeue (to exit). The entry is to insert an element at the end of rear, while the exit is to delete (or return) the element at the beginning of the table, front.

As in the case of stack 1, the stack can be implemented in the way of pointer and array. The author also introduced the array way before, this time using the single-linked list method.

First, define the structure of the queue:

struct Queue 
{ 
 ElementType Element; 
 Queue *Next; 
}; 

Main operations of queue ADT:

Queue *CreateQueue() 
{ 
 Queue *p = new Queue; 
 p->Next = NULL; 
 return p; 
} 
void Enqueue(Queue *rear, ElementType X) 
{ 
 Queue *p = new Queue; 
 p->Element = X; 
 rear->Next = p; 
 rear = p; 
} 
ElementType Dequeue(Queue *front) 
{ 
 Queue *p = front; 
 ElementType e = front->Element; 
 front = front->Next; 
 delete p; 
 return e; 
} 

Thank you for reading, I hope to help you, thank you for your support of this site!