The Note based on Data Structures and Algorithm Analysis in C CHAPTER 3 P2

The Note based on Data Structures and Algorithm Analysis in C

CHAPTER 3: Lists, Stacks, and Queues – Stacks && Queues

3. Stack ADT

3.1. Stack Model

A stack is a list with the restriction that inserts and deletes can be performed in only one position, namely the end of the list called the top. The fundamental operations on a stack are push, which is equivalent to an insert, and pop, which deletes the most recently inserted element.

Stacks are sometimes known as LIFO (last in, first out) lists. The usual operations to make empty stacks and test for emptiness are part of the repertoire, but essentially all that you can do to a stack is push and pop.

Figure 3.1.1. Stack model: input to a stack is by push, output is by pop

The general model is that there is some element that is at the top of the stack, and it is the only element that is visible.

Figure 3.1.2. Stack model: Stack model: only the top element is accessible

3.2. Implementation of Stacks

Of course, since a stack is a list, any list implementation will do. We will give two popular implementations. One uses pointers and the other uses an array.

3.2.1. Linked List Implementation of Stacks

The first implementation of a stack uses a singly linked list. We perform a

push by inserting at the front of the list. We perform a pop by deleting the element at the front of the list. A top operation merely examines the element at the front of the list, returning its value. Sometimes the pop and top operations are combined into one.

#ifndef _stack_h

struct Node;

typedef struct Node *PtrToNode;

typedef PtrToNode Stack;

int IsEmpty(Stack S);

Stack CreateStack(void);

void DisposeStack(Stack S);

void MakeEmpty(Stack S);

Void Push(ElementType X, Stack S);

ElementType Top(Stack S);

void Pop(Stack S);

#endif /*_Stack_h*/

/*Place in implementation file*/

/*Stack implementation is a linked list with a header*/

struct Node{

ElementType Element;

PtrToNode Next;

};

int

IsEmpty(Stack S){

return S -> Next == NULL;

}

//create an empty stack

Stack

CreateStack(void){

Stack S;

S = malloc(sizeof(struct Node));

if(S == NULL)

FatalError("Out of Space!!!");

S -> Next == NULL;

MakeEmpty(S);

return S;

}

void

MakeEmpty(Stack S){

if(S == NULL)

Error("Must use CreateSAtack first.");

else

while(!IsEmpty(S));

Pop(S);

}

void

Push (ElementType X, Stack S){

PtrToNode TmpCell;

TmpCell = malloc(sizeof(struct Node));

if(TmpCell == NULL)

FatalError("Out of Space!!!");

else{

TmpCell -> Element = X;

TmpCell -> Next = S -> Next;

S -> Next = TmpCell;

}

}

ElementType

Top(Stack S){

if(!IsEmpty(S))

return S -> Next -> Element;

Error("Empty stack");

return 0;/*return value to avoid warning*/

}

void

Pop(Stack S){

PtrToNode FirstCell;

if(IsEmpty(S));

Error("Empty stack");\

else{

FirstCell = S -> Next;

S -> Next = S -> Next -> Next;

free(FirstCell);

}

}

3.2.2. Array Implementation of Stacks

An alternative implementation avoids pointers and is probably the more popular solution. The only potential hazard with this strategy is that we need to declare an array size ahead of time.

#ifndef _stack_h

struct StackRecord;

typedef struct StackRecord *Stack;

int IsEmpty(Stack S);

int IsFull(Stack S);

Stack CreateStack(int MaxElements);

void DisposeStack(Stack S);

void MakeEmpty(Stack S);

Void Push(ElementType X, Stack S);

ElementType Top(Stack S);

void Pop(Stack S);

ElementType TopAndPop(Stack S);

#endif /*_Stack_h*/

/*Place in implementation file*/

/*Stack implementation is a dynamically allocated array*/

#define EmptyTOS (-1)

#define MinStackSize (5)

struct StackRecord{

int Capacity;

int TopOfStack;

ElementType *Array;

};

Stack

CreateStack(int MaxElements){

Stack S;

if(MaxElements < MinStackSize)

Error("Stack size is too small");

S = malloc(sizeof(struct StackRecord));

if(S == NULL)

FatalError("Out of Space!!!");

S -> Array = malloc(sizeof(ElementType) * MaxElements);

if(S -> Array == NULL)

FatalError("Out of Space!!!");

S -> Capacity = MaxElements;

MakeEmpty(S);

return S;

}

void

DisposeStack(Stack S){

if(S != NULL){

free(S -> Array);

free(S);

}

}

int

IsEmpty(Stack S){

return S -> TopOfStack == EmptyTOS;

}

void

MakeEmpty(Stack S){

S -> TopOfStack == EmptyTOS;

}

void

Push(ElementType X, Stack S){

if(IsFull(S))

Error("Full stack");

else

S -> Array[++S -> TopOfStack] = X;

}

ElementType

Top(Stack S){

if(!IsEmpty(s))

return S -> Array[S -> TopOfStack];

Error("Empty stack");

return 0;/*return value to avoid warning*/

}

void

Pop(Stack S){

if(IsEmpty(S))

Error("Empty stack");

else

S -> TopOfStack--;

}

ElementType

TopAndPop(Stack S){

if(!IsEmpty(S))

return S -> Array[S -> TopOfStack--];

Error("Empty stack");

return 0;/*return value to avoid warning*/

}

3.3. Application

3.3.1. Balancing Symbols

Compilers check your programs for syntax errors, but frequently a lack of one symbol (such as a missing brace or comment starter) will cause the compiler to spill out a hundred lines of diagnostics without identifying the real error. A useful tool in this situation is a program that checks whether everything is balanced.

Make an empty stack. Read characters until end of file. If the character is an open anything, push it onto the stack. If itis a close anything, then if the stack is empty report an error. Otherwise, pop the stack. If the symbol popped is not the corresponding opening symbol, then report an error. At end of file, if the stack is not empty report an error.

//Balancing Symbols -- Array Stack`

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct Mystack *Stack;

struct Mystack {

int Capacity;

int Top_of_stack; /*The sequence number of the Top*/

char *Array; /*The array stores elemebnts in the stack*/

};

//create a stack

Stack CreateStack(int Max)

{

Stack S;

S = malloc(sizeof(struct Mystack));

if (S == NULL)

printf("Create stack error!\n");

S->Array = malloc(sizeof(char) * Max);

if (S->Array == NULL)

printf("Create stack error!\n");

S->Capacity = Max;

S->Top_of_stack = 0;

return S;

}

//free the stack

void DisposeStack(Stack S)

{

if (S != NULL)

{

free(S->Array);

free(S);

}

}

//Is Empty?

int IsEmpty(Stack S)

{

return !S->Top_of_stack;

}

//Is Full?`

int IsFull(Stack S)

{

if (S->Top_of_stack == S->Capacity - 1)

return 1;

else

return 0;

}

//push an element into the stack

int Push(int x, Stack S)

{

if (IsFull(S))

printf("The Stack is full!\n");

else

S->Array[S->Top_of_stack++] = x;

}

//pop an element out the stack

int Pop(Stack S)

{

if (IsEmpty(S))

printf("The Stack is empty!\n");

else

S->Top_of_stack--;

}

//return the top value

char Top(Stack S)

{

if (!IsEmpty(S))

return S->Array[S->Top_of_stack--];

printf("The Stack is empty!\n");

return 0;

}

int main()

{

int i, len;

char str[100];

printf("Please input the symbol that you want to balance: \n");

scanf("%s", str);

len = strlen(str);

//create the stack base on the length of the text

struct Mystack *my_stack = CreateStack(len+1);

for (i = 0; i < len; i++)

{

if (str[i] == '{' || str[i] == '[' || str[i] == '(' )

Push(str[i], my_stack);

if (str[i] == '}')

{

if (Top(my_stack) == '{')

Pop(my_stack);

else

break;

}

else if (str[i] == ']')

{

if (Top(my_stack) == '[')

Pop(my_stack);

else

break;

}

else if (str[i] == ')')

{

if (Top(my_stack) == '(')

Pop(my_stack);

else

break;

}

}

if(IsEmpty(my_stack))

printf("The symbol that you input is balance!\n");

else

printf("The symbol that you input is imbalance!\n");

DisposeStack(my_stack);

return 0;

}

3.3.2. Postfix Expressions (It's been done before by C++)

This notation is known as postfix or reverse Polish notation. The easiest way to do this is to use a stack. When a number is seen, it is pushed onto the stack; when an operator is seen, the operator is applied to the two numbers (symbols) that are popped from the stack and the result is pushed onto the stack.

//postfix expressions

#include <iostream>

#include <stack>

#include <math.h>

using namespace std;

bool Number(char ch)//Number -> True

{

if (ch >= 48 && ch <= 57)

return true;

else

return false;

}

void InPut(char*& str)//get the nifix expression

{

cout << "Please Enter What You Want To calculation:" << endl;

while (1)

{

cin >> str;

if (Number(str[0]))//the first element of a nifix expression must be a number, else illegal

{

break;

}

else

{

cout << "Illegal Input,Please Input Again:";

delete[] str;

}

}

}

int GetPriority(char sy)//set the priority

{

switch (sy)

{

case '#':

return 0;

case '(':

return 1;

case '+':

case '-':

return 3;

case '*':

case '/':

return 5;

case ')':

return 6;

default:

return -1;

}

}

void AddSpace(char*& arr)//add space -> devide the character

{

*arr = ' ';

arr++;

}

char* GetBack()//get the postfix expression

{

char* middle = new char[30];

char* back = new char[30];

char* backend = back;

InPut(middle);

stack<char> s;

s.push('#');

while (*middle)

{

if (Number(*middle) || *middle == '.')//number || decimals -> print

{

*back = *middle;

back++, middle++;

}

else

{

if (Number(*(back - 1)))//if last element is a number

{

AddSpace(back);

}

if (*middle == ')')//if have a right bracket, exucting until meet the left bracket

{

while (s.top() != '(')

{

*back = s.top();

s.pop();

back++;

AddSpace(back);

}

middle++;

s.pop();//desert the left bracket

}

else if (*middle == '(')//if meet a laft bracket, push into stack

{

s.push(*middle); middle++;

}

else if (GetPriority(*middle) > GetPriority(s.top()))//inside operator's priority > outside operator's priority -> push

{

s.push(*middle); middle++;

}

else if (GetPriority(*middle) <= GetPriority(s.top())//inside operator's priority < outside operator's priority -> pop inside push outside

{

*back = s.top();

s.pop();

s.push(*middle);

back++; middle++;

AddSpace(back);

}

}

}

while (s.top() != '#')//print one by one

AddSpace(back);

*back = s.top();

s.pop(); back++;

}

*back = '\0';

cout << "The Back Is: " << backend << endl;

return backend;

}

double GetNumber(char*& arr)

{

//get the number > one digit

double sum[10] = { 0 }; int i = 0; double result = 0;

while (*arr != ' ')

{

sum[i] = *arr-48;

i++;

arr++;

}

int k = i - 1;

for (int j = 0; j < i; j++,k--)

{

result += (sum[j] * pow(10, k));

}

return result;

}

double Cauculate(char ch, double left, double right)//operation

{

switch (ch)

{

case '+':

return left + right;

case '-':

return left - right;

case '*':

return left * right;

case '/':

return left / right;

default:

return 0;

break;

}

}

double CountBack(char* back)

{

stack<double> s;

while (*back)

{

if (Number(*back))//meet number

{

s.push(GetNumber(back));//push into stack

}

else if (*back == ' ')

{

back++;//skip the space

}

else

{

double a = s.top();

s.pop();

double b = s.top();

s.pop();

s.push(Cauculate(*back, b, a));//meet an operator -> do calucation

back++;

}

}

while (s.size() >= 2)//until one dight

{

double a = s.top();

s.pop();

double b = s.top();

s.pop();

s.push(Cauculate(*back, b, a));

}

//return the result

return s.top();

}

void FunTest()

{

cout << "The Result Is: " <<CountBack(GetBack()) << endl;

}

int main()

{

FunTest();

system("pause");

return 0;

}

3.3.2. Tail Recursion

//a bad style

void

void printList(List L){

if(L != NULL){

PrintElement(L -> Element);

printList(L -> Next);

}

}

//reduce the memory

void

void printList(List L){

top:

if(L != NULL){

PrintElement(L -> Element);

L = L -> Next;

goto top;

}

}

4. The Queue ADT

4.1. Queue Model

The basic operations on a queue are enqueue, which inserts an element at the end of the list (called the rear), and dequeue, which deletes (and returns) the element at the start of the list (known as the front).

4.1.1 Queue Model

4.2. Array Implementation of Queues – Recursion Array

#ifdef _Queue_h

struct QueueRecord;

typedef struct Q ueueRecord *Queue;

int IsEmpty(Queue Q);

int IsFull(Queue Q);

Queue CreateQueue(Queue Q);

void DisposeQueue(Queue Q);

void MakeEmpty(Queue Q);

void EnQueue(ElementType X, Queue Q);

ElementType Front(Queue Q);

void Dequeue(Queue Q);

ElementType FrontAndDequeue(Queue Q);

#endif /*_Queue_h */

/* Place in implementation file */

/* Queue implementation is a dynamically allocated array */

#define MinQueueSize (5)

struct QueueRecord{

int Capacity;

int Front;

int Rear;

int Size;

ElementType *Array;

}

int IsEmpty(Queue Q){

return Q -> Size == 0;

}

void MakeEmpty(Queue Q){

Q -> Size = 0;

Q -> Front = 1;

Q -> Rear = 0;

}

static int Succ(int value, Queue Q){

if(++Value == Q -> Capacity)

Value = 0;

return Value;

}

void EnQueue(ElementType X, Queue Q){

if(IsFull(Q))

Error("Full queue");

else{

Q -> Size++;

Q -> Rear = Succ(Q -> Rear, Q);

Q -> Array[Q -> Rear] = X;

}

}

4.3. Application

When jobs are submitted to a printer, they are arranged in order of arrival. Thus, essentially, jobs sent to a line printer are placed on a queue.

Another example concerns computer networks. There are many network setups of personal computers in which the disk is attached to one machine, known as the file server. Users on other machines are given access to files on a first-come first-served basis, so the data structure is a queue.