작성자의 말 ¶
- 1학년때 엄한 방법으로 짠 스택과 큐를 다시 제대로 링크드리스트를 이용해서 짜보자!
- 스택은 자료구조 숙제 겸사겸사 해서 완료. 큐는 조만간 다시 만들 예정.
스택 ¶
#include<iostream> #include<string> using namespace std; struct Node { string data; Node * next; }; void push(Node **top, string argData); string pop(Node **top); string peek(Node *top); void erase(Node **top); void display(Node *top); int main() { Node * top=NULL; //Testing push push(&top, "임영동"); push(&top, "20021035"); push(&top, "컴퓨터공학과"); display(top); //Testing pop cout<<"Pop the top of the node: "<<pop(&top)<<endl; display(top); //Testing peek; cout<<"Peek the top of the node: "<<peek(top)<<endl; //Testing erase; erase(&top); display(top); return 0; } void push(Node **top, string argData) { Node * temp; temp=new Node; temp->data=argData; temp->next=*top;//Indicate the highest node of stack *top=temp;//Top links to the new element } string pop(Node **top) { Node * temp; string tempData; temp=*top; if(temp==NULL) {//If your stack is empty cout<<"Stack is empty now."<<endl; exit(1); } else {//If your stack has one element at least tempData=temp->data; *top=temp->next; delete temp; return tempData; } } string peek(Node *top) { string tempData; if(top==NULL) {//If your stack is empty cout<<"Stack is empty now."<<endl; exit(1); } else {//If your stack has one element at least tempData=top->data; return tempData; } } void erase(Node **top) { Node *temp; if(*top==NULL) {//If your stack is empty cout<<"Stack is empty now."<<endl; exit(1); } else { temp=*top; *top=(*top)->next; delete temp; } } void display(Node *top) { cout<<"----Stack----"<<endl; Node * tempNode; //Temporary node to tour linked list tempNode=top; do{ if(tempNode==NULL) { cout<<"Sorry... There is no node to display.\n"; break; } else { cout<<tempNode->data<<"\n"; if(tempNode->next==NULL)//Exit from do-while loop if value of next node is null break; else //Go to the next node if there is next node tempNode=tempNode->next; } }while(1); }
큐 ¶
~cpp #include<iostream.h> int num=0;//현재 사용중인 항목들의 수 int erase_num=0;//지운 항목 수를 세기 위한 수 int i; class List{ private: int data;//항목이 가진 값 List * next;//다음 항목을 가리키는 포인터 public: List(); List(int); ~List(); void add(int, List *); void erase(List *); void show(); void last(List *);//link와 last 메서드는 맨 마지막 항목의 void link(List *);//다음 항목을 가리키는 포인터를 NULL로 만들기 위한 함수 }; List::List() { data=0; next=NULL; } List::List(int temp) { data=temp; next=NULL; } List::~List() { delete next; } void List::add(int temp, List *n) { data=temp; next=n; num++; cout<<num<<"번째 항목에 "<<data<<"를 추가합니다.n"; } void List::erase(List *n) //f는 전, n은 다음 항목 { next=NULL; erase_num++; cout<<data<<"를 지웠습니다.n"; } void List::show() { cout<<"list["<<i<<"]: "<<" "; cout<<"주소값: "<<this<<"t"; cout<<"데이터 값: "<<data<<"t"; cout<<"다음 항목의 주소: "<<next<<endl; } void List::last(List *f) { f->next=this; next=NULL; } void List::link(List *n) { next=n; } int main() { int input, sub_input1; List * list=new List[10]; //우선 10개 동적 할당 do{ cout<<"==================LINKED LIST======================"<<endl; cout<<"1. 항목 추가"<<endl; cout<<"2. 항목 삭제"<<endl; cout<<"3. 항목 나열"<<endl; cout<<"4. 종료"<<endl; cout<<"==================================================="<<endl; cout<<"원하시는 메뉴를 선택해 주세요: "; cin>>input; switch(input){ case 1: if(num==10) cout<<"더 이상 추가할 수 없습니다.n"; else{ cout<<"추가할 항목의 값은? "; cin>>sub_input1; list[num].add(sub_input1, &list[num+1]); list[num-1].last(&list[num-2]); for(i=erase_num;i<num;i++) list[num].link(&list[num+1]); } break; case 2: if(num==0) cout<<"더 이상 지울 수 없습니다."<<endl; else{ list[erase_num].erase(&list[erase_num+1]); } break; case 3: for(i=erase_num;i<num;i++) list[i].show(); break; default: break; } }while(input!=4); cout<<"종료합니다."<<endl; return 0; }