Stacks and Queues for Day Two: Stack is abstract data type where elements inserted into stack using push model until entire stack is full. Elements/values can be removed using pop operation until entire stack is empty. This is a data type where last inserted elements are removed first. Stacks can be implemented in multiple ways, since stacks are considered abstract there is no implementation of stack data type in C or C++ (java does have a stack data type). There are many applications of this stack in day to day life. All the operations which do not have conditions like time frame or costs are executed using stack data structure. Toy Problem for Stacks: Let us implement stacks in C. We need to create user defined data type called stack. Also we need to create operations involving around this stack. We might as well create stacks using arrays but how do we remove a memory location? So this task implementing stacks using Linked Lists (Structure). Create linked list structure. Let us call the linked list as stack which can be represented with following structure: Create functions called push and pop. Notice when we insert an element into stack (top element) we are basically inserting values in first node. When we pop an element from stack we are removing element in the first node. Please be careful about memory allocation and handling the first node. Task on Stack Data Structure: Write a C program to calculate total sales and report transactions done by a coke vending machine. Soft drink (coke) tins are added into the vending machine one on top of the other. Each tin contains batch number, tin number, price for each tin. Money is accumulated when users buy the coke tins. Usually the tins on top are dispensed. Machine would no longer accept currency when stack is empty. typedef struct StackDataStructure{ int value; struct StackDataStructure *nextStackElement; }Stack; 1. Print out price, batch number and tin number when a can is popped out of machine. 2. Push method would add values of batch and tin number to the stack. 3. Calculate total sales. Queue: Queue is another abstract data structure which works exactly like a stack. In real world applications queues are mostly time bounded, so first come person/job gets served first like queue in banks, queue to board a train etc. The first person is called front of the queue (the most likely person to get served) and the last person is called rear. Just like stack a queue does not have data type in C or C++ (java on other hand has queue implementation in the language). Toy problem on queue: Let us create user defined data type in C using structures; we try to implement queues using linked lists. Create front and rear nodes. Initially when both front and rear nodes are NULL that means queue is empty. When we insert elements in queue front becomes the first node (for the first element rear is equal to front). More elements are added to the queue as rear. Deletion/Pop operation happens only to from element. Write a C program to implement above mentioned scenario. Task on Queue: When was the last time you visited a railway reservation counter? Assuming the south central railway decides to stream line their customer management at reservation counters (so that all the passengers get equal and right full services). They decided upon a token system where users are required to collect token when they enter reservation office. Multiple counters in the reservation office would display token numbers on LCD/monitor corresponding to the counter. typedef struct QueueDataType{ int value; struct QueueDataType *nextQueueElement; } Queue; Separate counters are installed for ladies, senior citizens and people with payments using credit cards. During token collection user chooses between L, S, C, and G options corresponding to ladies, senior citizens, credit card payers and general/other passengers. Each teller at a counter has next button, upon press the system should display next token number based on token collected by the passengers. Software should be able to deploy any where in the country only variable factor here is number of counters. Bigger the station, higher the number of counters. Stations with fewer counters can combine L/S/C into one option (called S means special). How to solve? 1. Write a structure to handle counter related information as follows: 2. Set initial counter values like G001 (general), L001 (ladies), S001 (seniors), C001 (credit cards) or SP001 (for special) as token numbers. 3. When the tokens are generated they are added to queue. We should need separate queues based on number of special counters (of smaller stations they might need only two queues; one for general and other for special). 4. Numbers of queues are not proportional to number of counters. Consider scenario of four counters for general and one counter for special. 5. Create structure for counter. Each counter can be represented as variable for this structure: typedef struct RailwayCounter{ char currentToken[10]; //token number char counterType; // l,g,c,s }Counter; typedef struct Station{ int numberOfCounters; int enableLadiesCounter; //0 or 1 int enableSeniorsCounter; //0 or 1 int enableCreditCardCounter; //0 or 1 int enableSpecialCounter; /* 0 or 1 special is enabled only when other privileged counters are combined. */ } ReservationOffice; 6. Based on number of counters in ReservationOffice we create Counter variables. 7. Write method called char* nextToken(Counter c); which will return next token number from the queue. 8. At the end the program should log all the token numbers inside a file with tab as delimiter. 9. Deliverables for this program would be: a. Methods to create a new reservation office b. Methods to choose and add passenger choice in the main queue program. c. Queue program to manage and dispense token numbers to appropriate counters. d. Managing special/ladies etc. queues separately e. Store all the counter information into a file. Evaluation Criteria: 1. Toy Problem in stacks 15% 2. Task on stacks 35% 3. Toy Problem in queue 10% 4. Task on queue 40%
hi , Go thru the C/C++ programming forum, it contains Stack and Queue implementation using Linked list(otherwise search the topic and go thru the article) After went thru it , u can change it according to ur need........ If u face any error discuss with us......... Try it of ur own........U can......
